package promote.brozen.algorithm.leetcode._062;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Brozen
 * @date 2020/9/6 10:29 AM
 * @email brozen@qq.com
 */
public class DifferentPath {

    /*
        f(m, 1) = 1;
        f(1, n) = 1;
        f(m, n) = f(m, n-1) + f(m-1, n)

        f(2, 2) = f(2, 1) + f(1, 2) = 2;
     */

    public int uniquePaths(int m, int n) {
        int[][] cache = new int[m + 1][];
        for (int i = 0; i < cache.length; i++) {
            cache[i] = new int[n + 1];
        }
        return paths(m, n, cache);
    }

    private int paths(int m, int n, int[][] cache) {
        if (m == 1 || n == 1) {
            cache[m][n] = 1;
            return 1;
        } else {
            if (cache[m][n] == 0) {
                return cache[m][n] = paths(m, n-1, cache) + paths(m-1, n, cache);
            } else {
                return cache[m][n];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new DifferentPath().uniquePaths(7, 3));
    }

}
